/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct Pair {
    char car;
    char cdr;
};

struct Pair* makeList(int listSize) {
    int i;
    struct Pair* result = (struct Pair*)malloc(sizeof (struct Pair*) * listSize);
    
    for (i = 0; i < listSize; i++) {
        struct Pair next = { 0, 0 };
        
        result[i] = next;
    }
    
    return result;
}

char get(struct Pair* map, int listSize, char key) {
    int i;
    
    for (i = 0; i < listSize; i++) {
        if (map[i].car == key) {
            return map[i].cdr;
        }
    }
    
    return 0;
}

void put(struct Pair* map, int listSize, char key, char value) {
    int i;
    
    for (i = 0; i < listSize; i++) {
        if (map[i].car == 0) {
            map[i].car = key;
            map[i].cdr = value;
            return;
        }
    }
}

int hasKey(struct Pair* map, int listSize, char key) {
    int i;
    
    for (i = 0; i < listSize; i++) {
        if (map[i].car == key) return 1;
    }
    
    return 0;
}

int hasValue(struct Pair* map, int listSize, char value) {
    int i;
    
    for (i = 0; i < listSize; i++) {
        if (map[i].cdr == value) return 1;
    }
    
    return 0;
}

void printList(struct Pair* map, int listSize) {
    int i;
    
    printf("(");
    
    for (i = 0; i < listSize; i++) {
        printf("(%d . %d) ", map[i].car, map[i].cdr);
    }
    
    printf(")\n");
}

char** findAndReplacePattern(char** words, int wordsSize, char* pattern, int* returnSize) {
    char** result = (char**)malloc(sizeof (char**) * (wordsSize));
    int i, j;
    
    for (i = 0, j = 0; i < wordsSize; i++) {
        if (checkWord(words[i], pattern)) {
            result[j] = words[i];
            j++;
        }
    }
    
    *returnSize = j;
    
    return result;
}

int checkWord(char* word, char* pattern) {
    struct Pair* map;
    
    int i;
    int result = 1;
    int wordSize = 0;
    
    while (word[wordSize] != NULL) {
        wordSize++;
    }
    
    map = makeList(wordSize);
    
    for (i = 0; i < wordSize; i++) {
        if (hasKey(map, wordSize, word[i])) {
            if (get(map, wordSize, word[i]) != pattern[i]) {
                result = 0;
                break;
            }
        }
        else if (hasValue(map, wordSize, pattern[i])) {
            result = 0;
            break;
        }
        else {
            put(map, wordSize, word[i], pattern[i]);
        }
    }
    
    
    free(map);
    
    return result;
}

